// $Id: string.cpp 2 2009-09-02 08:47:42Z joseph2002 $
/*
 * Copyright 2008-2009 Joseph Wu
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 *
 * For more information, see http://xpcomplus.sourceforge.net
 */

#define XPCOM_SOURCE

#include <xpcom/config.hpp>
#include <algorithm>
#include <xpcom/exception.hpp>
#include <xpcom/string.hpp>
#include "api/string.hpp"

namespace xpcom {

namespace {

//
// Templatized string API
//
template <typename CharT>
class string_api;

template <>
class string_api<char>
{
public:
    typedef char char_type;
    typedef basic_string<char_type> string_type;
    typedef uint32_t size_type;
    typedef uint32_t index_type;

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    enum
    {
        init_depend = NS_CSTRING_CONTAINER_INIT_DEPEND,
        init_adopt = NS_CSTRING_CONTAINER_INIT_ADOPT,
        init_substring = NS_CSTRING_CONTAINER_INIT_SUBSTRING
    };
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static result_t init(string_type& str) throw()
    {
        return ::NS_CStringContainerInit(str);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    static result_t init2(
            string_type& str,
            const char_type* data = 0,
            size_type len = size_type(-1),
            uint32_t flags = 0) throw()
    {
        return ::NS_CStringContainerInit2(str, data, len, flags);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static void finish(string_type& str) throw()
    {
        ::NS_CStringContainerFinish(str);
    }

    static size_type get_data(
            const string_type& str,
            const char_type** data, bool_t* terminated = 0) throw()
    {
        return ::NS_CStringGetData(str, data, terminated);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    static size_type get_mutable_data(
            string_type& str,
            size_type len, char_type** data) throw()
    {
        return ::NS_CStringGetMutableData(str, len, data);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static char_type* clone_data(const string_type& str) throw()
    {
        return ::NS_CStringCloneData(str);
    }

    static result_t set_data(
            string_type& str,
            const char_type* data, size_type len = size_type(-1)) throw()
    {
        return ::NS_CStringSetData(str, data, len);
    }

    static result_t set_data_range(
            string_type& str,
            index_type cut_offset, size_type cut_len,
            const char_type* data, size_type len = size_type(-1)) throw()
    {
        return ::NS_CStringSetDataRange(str, cut_offset, cut_len, data, len);
    }

    static result_t copy(
            string_type& dest_str, const string_type& src_str) throw()
    {
        return ::NS_CStringCopy(dest_str, src_str);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_9
    static void set_is_void(string_type& str, const bool_t is_void) throw()
    {
        ::NS_CStringSetIsVoid(str, is_void);
    }

    static bool_t get_is_void(const string_type& str) throw()
    {
        return ::NS_CStringGetIsVoid(str);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_9
};

template <>
class string_api<wchar>
{
public:
    typedef wchar char_type;
    typedef basic_string<char_type> string_type;
    typedef uint32_t size_type;
    typedef uint32_t index_type;

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    enum
    {
        init_depend = NS_STRING_CONTAINER_INIT_DEPEND,
        init_adopt = NS_STRING_CONTAINER_INIT_ADOPT,
        init_substring = NS_STRING_CONTAINER_INIT_SUBSTRING
    };
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static result_t init(string_type& str) throw()
    {
        return ::NS_StringContainerInit(str);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    static result_t init2(
            string_type& str,
            const char_type* data = 0,
            size_type len = size_type(-1),
            uint32_t flags = 0) throw()
    {
        return ::NS_StringContainerInit2(str, data, len, flags);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static void finish(string_type& str) throw()
    {
        ::NS_StringContainerFinish(str);
    }

    static size_type get_data(
            const string_type& str,
            const char_type** data, bool_t* terminated = 0) throw()
    {
        return ::NS_StringGetData(str, data, terminated);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8
    static size_type get_mutable_data(
            string_type& str,
            size_type len, char_type** data) throw()
    {
        return ::NS_StringGetMutableData(str, len, data);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_8

    static char_type* clone_data(const string_type& str) throw()
    {
        return ::NS_StringCloneData(str);
    }

    static result_t set_data(
            string_type& str,
            const char_type* data, size_type len = size_type(-1)) throw()
    {
        return ::NS_StringSetData(str, data, len);
    }

    static result_t set_data_range(
            string_type& str,
            index_type cut_offset, size_type cut_len,
            const char_type* data, size_type len = size_type(-1)) throw()
    {
        return ::NS_StringSetDataRange(str, cut_offset, cut_len, data, len);
    }

    static result_t copy(
            string_type& dest_str, const string_type& src_str) throw()
    {
        return ::NS_StringCopy(dest_str, src_str);
    }

#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_9
    static void set_is_void(string_type& str, const bool_t is_void) throw()
    {
        ::NS_StringSetIsVoid(str, is_void);
    }

    static bool_t get_is_void(const string_type& str) throw()
    {
        return ::NS_StringGetIsVoid(str);
    }
#endif // XPCOM_API_VERSION >= XPCOM_API_VERSION_1_9
};

template <typename CharT>
int string_compare_aux(
        const CharT* s1, uint32_t n1, const CharT* s2, uint32_t n2)
{
    const int cmp = char_traits<CharT>::compare(s1, s2, (std::min)(n1, n2));
    return cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0));
}

} // anonymous namespace

template <typename CharT>
inline void
basic_string<CharT>::init()
{
    string_api<value_type>::init(*this) | throw_exception;
}

template <typename CharT>
inline void
basic_string<CharT>::init(const value_type* s, size_type n, uint32_t flags)
{
    string_api<value_type>::init2(*this, s, n, flags) | throw_exception;
}

template <typename CharT>
void
basic_string<CharT>::init(size_type n, value_type c)
{
    if (n == 0) {
        init();
    } else if (n == 1) {
        init(&c, size_type(1));
    } else {
        init();

        mutable_data_type d;
        get_mutable_data(d, n);
        if (!d.data) {
            finish();
            throw_bad_alloc();
        }

        try {
            traits_type::assign(d.data, d.length, c);
        } catch (...) {
            finish();
            throw;
        }
    }
}

template <typename CharT>
inline void
basic_string<CharT>::init_adopt(const value_type* s, size_type n)
{
    init(s, n, string_api<value_type>::init_adopt);
}

template <typename CharT>
inline void
basic_string<CharT>::init_depend(const value_type* s, size_type n)
{
    init(s, n, string_api<value_type>::init_depend);
}

template <typename CharT>
inline void
basic_string<CharT>::finish()
{
    string_api<value_type>::finish(*this);
}

template <typename CharT>
inline const typename basic_string<CharT>::value_type*
basic_string<CharT>::data() const
{
    const value_type* p;
    string_api<value_type>::get_data(*this, &p, 0);
    return p;
}

template <typename CharT>
inline typename basic_string<CharT>::value_type*
basic_string<CharT>::mutable_data()
{
    value_type* p;
    string_api<value_type>::get_mutable_data(*this, npos, &p);
    return p;
}

template <typename CharT>
inline void
basic_string<CharT>::get_data(data_type& data) const
{
    data.length = string_api<value_type>::get_data(*this, &data.data, 0);
}

template <typename CharT>
inline void
basic_string<CharT>::get_mutable_data(mutable_data_type& data, size_type len)
{
    data.length =
        string_api<value_type>::get_mutable_data(*this, len, &data.data);
}

template <typename CharT>
basic_string<CharT>::basic_string()
{
    init();
}

template <typename CharT>
basic_string<CharT>::basic_string(const basic_string& s)
{
    init();

    result r = string_api<value_type>::copy(*this, s);
    if (r.failed()) {
        finish();
        throw_exception(r);
    }
}

template <typename CharT>
basic_string<CharT>::basic_string(
        const basic_string& s, size_type pos, size_type n)
{
    data_type d;
    s.get_data(d);

    if (pos > d.length)
        throw_out_of_range();

    init(d.data + pos, (std::min)(n, d.length - pos));
}

template <typename CharT>
basic_string<CharT>::basic_string(const value_type* s, size_type n)
{
    init(s, n);
}

template <typename CharT>
basic_string<CharT>::basic_string(size_type n, value_type c)
{
    init(n, c);
}

template <typename CharT>
basic_string<CharT>::~basic_string()
{
    finish();
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::assign(const basic_string& s)
{
    if (this != &s)
        string_api<value_type>::copy(*this, s) | throw_exception;
    return *this;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::assign(const basic_string& s, size_type pos, size_type n)
{
    data_type d;
    s.get_data(d);

    if (pos > d.length)
        throw_out_of_range();

    string_api<value_type>::set_data(
            *this, d.data + pos, (std::min)(n, d.length - pos))
            | throw_exception;
    return *this;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::assign(const value_type* s, size_type n)
{
    string_api<value_type>::set_data(*this, s, n) | throw_exception;
    return *this;
}

template <typename CharT>
inline typename basic_string<CharT>::const_iterator
basic_string<CharT>::begin() const
{
    return data();
}

template <typename CharT>
inline typename basic_string<CharT>::iterator
basic_string<CharT>::begin()
{
    return mutable_data();
}

template <typename CharT>
inline typename basic_string<CharT>::const_iterator
basic_string<CharT>::end() const
{
    data_type d;
    get_data(d);
    return d.data + d.length;
}

template <typename CharT>
inline typename basic_string<CharT>::iterator
basic_string<CharT>::end()
{
    mutable_data_type d;
    get_mutable_data(d);
    return d.data + d.length;
}

template <typename CharT>
inline typename basic_string<CharT>::size_type
basic_string<CharT>::size() const
{
    const value_type* data;
    return string_api<value_type>::get_data(*this, &data, 0);
}

template <typename CharT>
void
basic_string<CharT>::resize(size_type n, value_type c)
{
    size_type len = size();
    if (n != len) {
        mutable_data_type d;
        get_mutable_data(d, n);

        if (!d.data)
            throw_bad_alloc();

        if (d.length > len)
            traits_type::assign(d.data + len, d.length - len, c);
    }
}

template <typename CharT>
void
basic_string<CharT>::clear()
{
#if XPCOM_API_VERSION >= XPCOM_API_VERSION_1_9
    string_api<value_type>::set_is_void(*this, true_);
#else
    value_type* data;
    string_api<value_type>::get_mutable_data(*this, 0, &data); // truncate
#endif
}

template <typename CharT>
typename basic_string<CharT>::const_reference
basic_string<CharT>::at(size_type pos) const
{
    data_type d;
    get_data(d);

    if (pos >= d.length)
        throw_out_of_range();

    return *(d.data + pos);
}

template <typename CharT>
typename basic_string<CharT>::reference
basic_string<CharT>::at(size_type pos)
{
    mutable_data_type d;
    get_mutable_data(d);

    if (pos >= d.length)
        throw_out_of_range();

    return *(d.data + pos);
}

template <typename CharT>
typename basic_string<CharT>::iterator
basic_string<CharT>::insert(iterator i, value_type c)
{
    XPCOM_ASSERT(i >= begin() && i <= end());

    const size_type pos = i - begin();
    replace(pos, size_type(0), &c, size_type(1));
    return begin() + pos;
}

template <typename CharT>
typename basic_string<CharT>::iterator
basic_string<CharT>::erase(iterator i1, iterator i2)
{
    XPCOM_ASSERT(begin() <= i1 && i1 <= i2 && i2 <= end());

    const size_type pos = i1 - begin();
    replace(pos, i2 - i1, static_cast<const value_type*>(0), size_type(0));
    return begin() + pos;
}

template <typename CharT>
typename basic_string<CharT>::iterator
basic_string<CharT>::erase(iterator i)
{
    XPCOM_ASSERT(i >= begin() && i < end());

    const size_type pos = i - begin();
    replace(pos, size_type(1), static_cast<const value_type*>(0), size_type(0));
    return begin() + pos;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::replace(size_type pos, size_type n, const basic_string& s)
{
    check_pos(pos);

    data_type d;
    s.get_data(d);

    string_api<value_type>::set_data_range(
            *this, pos, n, d.data, d.length) | throw_exception;

    return *this;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::replace(
        size_type pos1, size_type n1,
        const basic_string& s, size_type pos2, size_type n2)
{
    check_pos(pos1);

    data_type d;
    s.get_data(d);

    if (pos2 > d.length)
        throw_out_of_range();

    string_api<value_type>::set_data_range(
            *this, pos1, n1, d.data + pos2, (std::min)(n2, d.length - pos2))
            | throw_exception;

    return *this;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::replace(
        size_type pos, size_type n1, const value_type* s, size_type n2)
{
    string_api<value_type>::set_data_range(
            *this, check_pos(pos), n1, s, n2) | throw_exception;
    return *this;
}

template <typename CharT>
basic_string<CharT>&
basic_string<CharT>::replace(
        size_type pos, size_type n1, size_type n2, value_type c)
{
    if (n2 == 0) {
        string_api<value_type>::set_data_range(
                *this, check_pos(pos), n1, 0, 0) | throw_exception;
    } else if (n2 == 1) {
        string_api<value_type>::set_data_range(
                *this, check_pos(pos), n1, &c, size_type(1)) | throw_exception;
    } else {
        replace(pos, n1, basic_string(n2, c));
    }

    return *this;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::copy(value_type* s, size_type n, size_type pos) const
{
    XPCOM_ASSERT(s);

    data_type d;
    get_data(d);

    if (pos > d.length)
        throw_out_of_range();

    const size_type len = (std::min)(n, d.length - pos);
    if (len > 0)
        traits_type::copy(s, d.data + pos, len);

    return len;
}

template <typename CharT>
void
basic_string<CharT>::swap(basic_string& s)
{
    std::swap(data_, s.data_);
}

template <typename CharT>
typename basic_string<CharT>::value_type*
basic_string<CharT>::clone_data() const
{
    if (empty())
        return 0;

    value_type* p = string_api<value_type>::clone_data(*this);
    if (!p)
        throw_bad_alloc();

    return p;
}

template <typename CharT>
typename basic_string<CharT>::value_type*
basic_string<CharT>::release_data(size_type* n)
{
    // FIXME XPCOM does not provide something like detach or release data, so
    //       we have to clone it...
    value_type* p = 0;
    size_type len = size();

    if (len > 0) {
        p = string_api<value_type>::clone_data(*this);
        if (!p)
            throw_exception(); // not throw_bad_alloc()

        clear();
    }

    if (n)
        *n = len;
    return p;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find(const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return find(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return find(s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    // Null string always matches (if inside string)
    if (n == 0)
        return pos <= d.length ? pos : npos;

    if (n <= d.length) {
        for ( ; pos <= d.length - n; ++pos) {
            if (traits_type::eq(d.data[pos], s[0]) &&
                traits_type::compare(d.data + pos + 1, s + 1, n - 1) == 0)
            {
                return pos;
            }
        }
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find(value_type c, size_type pos) const
{
    size_type ret = npos;

    data_type d;
    get_data(d);

    if (pos < d.length) {
        const size_type n = d.length - pos;
        const value_type* r = traits_type::find(d.data + pos, n, c);
        if (r)
            ret = r - d.data;
    }

    return ret;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::rfind(const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return rfind(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::rfind(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return rfind(s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::rfind(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    // Null always matches
    if (n == 0)
        return (std::min)(pos, d.length);

    if (n <= d.length) {
        pos = (std::min)(d.length - n, pos);
        do {
            if (traits_type::compare(d.data + pos, s, n) == 0)
                return pos;
        } while (pos-- > 0);
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::rfind(value_type c, size_type pos) const
{
    data_type d;
    get_data(d);

    size_type size = d.length;

    if (size > 0) {
        if (--size > pos)
            size = pos;

        for (++size; size-- > 0; ) {
            if (traits_type::eq(d.data[size], c))
                return size;
        }
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_of(const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return find_first_of(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_of(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return find_first_of(
            s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_of(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    if (n > 0) {
        for ( ; pos < d.length; ++pos) {
            const value_type* r = traits_type::find(s, n, d.data[pos]);
            if (r)
                return pos;
        }
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_of(value_type c, size_type pos) const
{
    return find(c, pos);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_of(const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return find_last_of(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_of(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return find_last_of(
            s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_of(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    size_type size = d.length;

    if (size > 0 && n > 0) {
        if (--size > pos)
            size = pos;

        do {
            if (traits_type::find(s, n, d.data[size]))
                return size;
        } while (size-- != 0);
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_of(value_type c, size_type pos) const
{
    return rfind(c, pos);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_not_of(
        const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return find_first_not_of(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_not_of(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return find_first_not_of(
            s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_not_of(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    for ( ; pos < d.length; ++pos) {
        if (!traits_type::find(s, n, d.data[pos]))
            return pos;
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_first_not_of(value_type c, size_type pos) const
{
    data_type d;
    get_data(d);

    for ( ; pos < d.length; ++pos) {
        if (!traits_type::eq(d.data[pos], c))
            return pos;
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_not_of(
        const basic_string& s, size_type pos) const
{
    data_type d;
    s.get_data(d);
    return find_last_not_of(d.data, pos, d.length);
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_not_of(const value_type* s, size_type pos) const
{
    XPCOM_ASSERT(s);
    return find_last_not_of(
            s, pos, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_not_of(
        const value_type* s, size_type pos, size_type n) const
{
    XPCOM_ASSERT(s || n == 0);

    data_type d;
    get_data(d);

    size_type size = d.length;

    if (size > 0) {
        if (--size > pos)
            size = pos;

        do {
            if (!traits_type::find(s, n, d.data[size]))
                return size;
        } while (size--);
    }

    return npos;
}

template <typename CharT>
typename basic_string<CharT>::size_type
basic_string<CharT>::find_last_not_of(value_type c, size_type pos) const
{
    data_type d;
    get_data(d);

    size_type size = d.length;

    if (size > 0) {
        if (--size > pos)
            size = pos;

        do {
            if (!traits_type::eq(d.data[size], c))
                return size;
        } while (size--);
    }

    return npos;
}

template <typename CharT>
basic_string<CharT>
basic_string<CharT>::substr(size_type pos, size_type n) const
{
    data_type d;
    get_data(d);

    if (pos > d.length)
        throw_out_of_range();

    // If acquiring the whole string, return this to avoid copying
    if (pos == 0 && (n == npos || n == d.length)) {
        return *this;
    } else {
        // XXX Do not use init_substring flag,
        // cause we need to keep the string null-terminated
        return basic_string(d.data + pos, (std::min)(n, d.length - pos));
    }
}

template <typename CharT>
int basic_string<CharT>::compare(const basic_string& s) const
{
    data_type d1, d2;
    get_data(d1);
    s.get_data(d2);

    return string_compare_aux(d1.data, d1.length, d2.data, d2.length);
}

template <typename CharT>
int basic_string<CharT>::compare(
        size_type pos1, size_type n1, const basic_string& s) const
{
    data_type d1, d2;
    get_data(d1);
    s.get_data(d2);

    if (pos1 > d1.length)
        throw_out_of_range();

    return string_compare_aux(
            d1.data + pos1, (std::min)(n1, d1.length - pos1),
            d2.data, d2.length);
}

template <typename CharT>
int basic_string<CharT>::compare(
        size_type pos1, size_type n1, const basic_string& s,
        size_type pos2, size_type n2) const
{
    data_type d1, d2;
    get_data(d1);
    s.get_data(d2);

    if (pos1 > d1.length || pos2 > d2.length)
        throw_out_of_range();

    return string_compare_aux(
            d1.data + pos1, (std::min)(n1, d1.length - pos1),
            d2.data + pos2, (std::min)(n2, d2.length - pos2));
}

template <typename CharT>
int basic_string<CharT>::compare(const value_type* s) const
{
    XPCOM_ASSERT(s);

    data_type d;
    get_data(d);

    return string_compare_aux(
            d.data, d.length,
            s, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
int basic_string<CharT>::compare(
        size_type pos1, size_type n1, const value_type* s) const
{
    XPCOM_ASSERT(s);

    data_type d;
    get_data(d);

    if (pos1 > d.length)
        throw_out_of_range();

    return string_compare_aux(
            d.data + pos1, (std::min)(n1, d.length - pos1),
            s, static_cast<size_type>(traits_type::length(s)));
}

template <typename CharT>
int basic_string<CharT>::compare(
        size_type pos1, size_type n1, const value_type* s, size_type n2) const
{
    XPCOM_ASSERT(s || n2 == 0);

    data_type d;
    get_data(d);

    if (pos1 > d.length)
        throw_out_of_range();

    return string_compare_aux(
            d.data + pos1, (std::min)(n1, d.length - pos1), s, n2);
}

template <typename CharT>
bool basic_string<CharT>::operator==(const basic_string<CharT>& rhs) const
{
    data_type d1, d2;
    get_data(d1);
    rhs.get_data(d2);

    return d1.length == d2.length &&
            traits_type::compare(d1.data, d2.data, d1.length) == 0;
}

// Explicit instantiations
template class XPCOM_DECL basic_string<char>;
template class XPCOM_DECL basic_string<wchar>;
#if defined(BOOST_MSVC) && BOOST_MSVC >= 1400
template XPCOM_DECL
basic_string<char>::basic_string(char*, char*);
template XPCOM_DECL
basic_string<char>::basic_string(const char*, const char*);
template XPCOM_DECL
basic_string<wchar>::basic_string(wchar*, wchar*);
template XPCOM_DECL
basic_string<wchar>::basic_string(const wchar*, const wchar*);
#endif

} // namespace xpcom
